/*
 * @Author: _LJP 2634716776@qq.com
 * @Date: 2024-01-29 19:52:06
 * @LastEditors: _LJP 2634716776@qq.com
 * @LastEditTime: 2024-02-01 18:58:16
 * @FilePath: /my_-linux/Pro24/Hashi/unordered/HashTable/hashTable.h
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置
 * 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */

//***************************************

//*******开散列(开链法)哈希表的实现*******
//***************************************
/*开放定址法*/

#include <iostream>
#include <string>
#include <vector>

template <class K, class V>
struct HashNode {
  // 哈希表的节点设置
  typedef HashNode<K, V> Node;
  Node* _next = nullptr;
  std::pair<K, V> _kv;

  HashNode(const std::pair<K, V> kv) : _kv(kv) {}
};

template <class K>
struct HashFunc {
  size_t operator()(const K& key) {
    // std::cout << key << std::endl;
    return (size_t)key;
  }
  
};

template <>
struct HashFunc<std::string> {
  size_t operator()(const std::string& key) {
    size_t hash = 0;
    for (auto it : key) {
      hash += it;

      hash *= 31;
    }
    // std::cout << hash << std::endl;
    return hash;
  }
};

template <class K, class V, class Hash = HashFunc<K>>
class HashTable {
 public:
  typedef HashNode<K, V> Node;

  ~HashTable() {
    Node* cur = nullptr;
    for (size_t i = 0; i < _hashtable.size(); ++i) {
      if (_hashtable[i]) {
        cur = _hashtable[i];
        Node* next = cur->_next;
        while (cur) {
          delete cur;
          cur = next;
        }
      }
    }
  }

  bool Insert(const std::pair<K, V> kv) {
    Hash to_int;

    // 使用Find函数进行判断是否需要进行插入(需要预防除零错误)
    if (Find(kv.first)) {
      // 找到该数据说明该数据存在不予继续插入
      return false;
    }

    if (_n == _hashtable.size()) {
      // 判断负载因子是否为1 负载因子若是为1则进行扩容
    //   size_t newsize = _hashtable.size() == 0 ? 10 : _hashtable.size() * 2;
      size_t newsize = GetNextPrime(_hashtable.size());
      std::vector<Node*> newTable;
      newTable.resize(newsize);

      // for(Node *&cur : _hashtable) 遍历Node*指针数组
      for (auto& cur : _hashtable) {
        while (cur) {
          Node* next = cur->_next;
          size_t hashi = to_int(cur->_kv.first) % newTable.size();
          cur->_next = newTable[hashi];
          newTable[hashi] = cur;
          cur = next;
        }
      }
      _hashtable.swap(newTable);
    }

    // 正常插入
    Node* newnode = new Node(kv);
    size_t hashi = to_int(kv.first) % _hashtable.size();
    // std::cout << kv.first <<std::endl;
    newnode->_next = _hashtable[hashi];
    _hashtable[hashi] = newnode;
    ++_n;
    return true;
  }

  Node* Find(const K& key) {
    Hash to_int;

    if (_hashtable.size() == 0) return nullptr;  // 防止除零错误

    size_t hashi = to_int(key) % _hashtable.size();
    Node* cur = _hashtable[hashi];

    while (cur) {
      if (cur->_kv.first == key) {
        return cur;
      }
      cur = cur->_next;
    }
    return nullptr;
  }

  bool Erase(const K& key) {
    Hash to_int;
    if (_hashtable.size() == 0) return false;  // 防止空的情况继续删除

    size_t hashi = to_int(key) % _hashtable.size();

    Node* cur = _hashtable[hashi];
    Node* prev = nullptr;
    while (cur) {
      if (cur->_kv.first == key) {
        if (prev) {
          prev->_next = cur->_next;
        } else {
          _hashtable[hashi] = cur->_next;
        }
        delete cur;
        return true;
      } else {
        prev = cur;
        cur = cur->_next;
      }
    }
    return false;
  }

  /*
          迭代器以及后序封装的要点

          1.在当前模型下只能完成对整型类型数据的存储,不能完成其他类型数据的存储(使用仿函数的方式完成其他类型数据的存储)
                  1.1
         除此之外完成解决第一点的方案后的问题为该模型不能很好的对string类型数据进行存储
                          本质的原因是因为string类型不支持取模%操作,且其不能转化为size_t类型;
                          解决办法为另加一个仿函数,关键点有用到素数对应的乘数因子;
                  1.2 在扩容当中可以采用素数列表进行扩容,防止哈希冲突

          2.迭代器的封装
     迭代器需要的传值为两个分别为哈希表本表以及v一个节点的指针;
                在实现哈希表的迭代器时因为哈希表的迭代器为一个单向的迭代器,所以对于单向的迭代器而言重点需要实现它的operator++();
                迭代器实现的相关问题为++的重载实现的思路;
                2.1
     哈希表的迭代器在实现当中出现重复引用的问题需要进行类模板的声明; 2.2
         哈希表的迭代器在实现当中由于传入了哈希表的指针,由于需要访问哈希表中的私有变量vector中的size(),可以
                        在迭代器的实现当中定义类友元或者是给定一个gettable的函数(传入对应的哈希表中的vector)来访问其中的私有成员;
  */

  void Check() {
    // 检查函数 没有太重要的意义
    int i = 0;
    for (auto cur : _hashtable) {
      std::cout << "(" << i << ")"
                << " == ";
      if (cur) {
        while (cur) {
          std::cout << cur->_kv.first << " : " << cur->_kv.second << " || ";
          cur = cur->_next;
        }
        std::cout << std::endl;
      } else {
        std::cout << "nullptr" << std::endl;
      }
      ++i;
    }
  }

 protected:
  size_t GetNextPrime(size_t prime) {
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53,        97,         193,        389,       769,       1543,
        3079,      6151,       12289,      24593,     49157,     98317,
        196613,    393241,     786433,     1572869,   3145739,   6291469,
        12582917,  25165843,   50331653,   100663319, 201326611, 402653189,
        805306457, 1610612741, 3221225473, 4294967291};
    size_t i = 0;
    for (; i < __stl_num_primes; ++i) {
      if (__stl_prime_list[i] > prime) return __stl_prime_list[i];
    }
    return __stl_prime_list[i];
  }

 private:
  std::vector<Node*> _hashtable;  // 哈希表整体构造
  size_t _n = 0;                  // 负载因子
};
